LeetCode 143、重排链表

一、题目描述

给定一个单链表 L：L0→L1→…→Ln-1→Ln ，

将其重新排列后变为：L0→Ln→L1→Ln-1→L2→Ln-2→…

你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

示例1:

给定链表 1->2->3->4->5, 重新排列为 1->5->2->4->3.

示例2：

给定链表 1->2->3->4, 重新排列为 1->4->2->3.

二、题目解析

这道题目很考察基本功和观察能力，最终的结果就是将原链表的前半部分和原链表的后半部分反转之后的链表进行合并得到的。

所以，需要执行以下三个操作。

• 1、寻找出原链表的中点，把链表划分为两个区域
• 2、将右边的链表进行反转
• 3、把这两个区域进行交错合并

1、使用快慢指针寻找链表中点

在链表的头节点设置两个指针 slow、fast，同时将它们向后移动。

每一次，slow 向后移动一步，fast 向后移动两步。

于是，找到了中间节点 5，把链表划分为两个区域。

2、将右边的链表进行反转

3、把这两个区域进行交错合并

属于归并排序的降维版本，这个操作不了解的话可以复习一下归并排序。

三、参考代码

1、Java 代码

// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
// 作者：程序员吴师兄
// 代码有看不懂的地方一定要私聊咨询吴师兄呀
// 重排链表（LeetCode 143）：https://leetcode.cn/problems/reorder-list/
class Solution {
    public void reorderList(ListNode head) {
    // a、寻找出原链表的中点，把链表划分为两个区域
        // b、将右边的链表进行反转
        // c、把这两个区域进行交错合并
      
        // 1、使用快慢指针寻找出链表的中点来 
       // ********
        // 对于 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8
        // 中间节点值为 5
        // 所以左边区域为 1 -> 2 -> 3 -> 4 -> 5
        // 右边区域为 6 -> 7 -> 8
        // 但在视频讲解中，我把 5 归为了右边区域，这是一个错误
        // 虽然这个错误并不影响结果，因为合并过程都是一样的逻辑
        // ********
        ListNode mid = middleNode(head);

        // 2、基于 mid 这个中点，将链表划分为两个区域

        // 左边的区域开头节点是 head
        ListNode leftHead = head;

        // 右边的区域开头节点是 mid.next
        ListNode rightHead = mid.next;

        // 将链表断开，就形成了两个链表了
        mid.next = null;

        // 3、将右边的链表进行反转
        rightHead = reverseList(rightHead);

        // 4、将这两个链表进行合并操作，即进行【交错拼接】
        while( leftHead != null && rightHead != null){

            // 拼接过程如下
            // 5、先记录左区域、右区域【接下来将有访问的两个节点】
            ListNode leftHeadNext = leftHead.next;

            ListNode rightHeadNext = rightHead.next;

            // 6、左边连接右边的开头
            leftHead.next = rightHead;

            // 7、leftHead 已经处理好，移动到下一个节点，即刚刚记录好的节点
            leftHead = leftHeadNext;

            // 8、右边连接左边的开头
            rightHead.next = leftHead;

            // 9、rightHead 已经处理好，移动到下一个节点，即刚刚记录好的节点
            rightHead = rightHeadNext;
            
        }

    }

    // LeetCode 876 : 链表的中间节点
    public ListNode middleNode(ListNode head) {

        ListNode fast = head;

        ListNode slow = head;

        while(fast != null && fast.next != null){

            fast = fast.next.next;

            slow = slow.next;
        }

        return slow;

    }

    // LeetCode 206 : 反转链表
    public ListNode reverseList(ListNode head) {

        // 寻找递归终止条件
        // 1、head 指向的结点为 null 
        // 2、head 指向的结点的下一个结点为 null 
        // 在这两种情况下，反转之后的结果还是它自己本身
        if( head == null || head.next == null)  return head;

        // 不断的通过递归调用，直到无法递归下去，递归的最小粒度是在最后一个节点
        // 因为到最后一个节点的时候，由于当前节点 head 的 next 节点是空，所以会直接返回 head
        ListNode cur = reverseList(head.next);

        // 比如原链表为 1 --> 2 --> 3 --> 4 --> 5
        // 第一次执行下面代码的时候，head 为 4，那么 head.next = 5
        // 那么 head.next.next 就是 5.next ，意思就是去设置 5 的下一个节点
        // 等号右侧为 head，意思就是设置 5 的下一个节点是 4

        // 这里出现了两个 next
        // 第一个 next 是「获取」 head 的下一节点
        // 第二个 next 是「设置」 当前节点的下一节点为等号右侧的值
        head.next.next = head;


        // head 原来的下一节点指向自己，所以 head 自己本身就不能再指向原来的下一节点了
        // 否则会发生无限循环
        head.next = null;

        // 我们把每次反转后的结果传递给上一层
        return cur;
    }
}

2、C++ 代码

class Solution {
public:
    void reorderList(ListNode*  head) {
        // a、寻找出原链表的中点，把链表划分为两个区域
        // b、将右边的链表进行反转
        // c、把这两个区域进行交错合并
      
        // 1、使用快慢指针寻找出链表的中点来 
        // ********
        // 对于 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8
        // 中间节点值为 5
        // 所以左边区域为 1 -> 2 -> 3 -> 4 -> 5
        // 右边区域为 6 -> 7 -> 8
        // 但在视频讲解中，我把 5 归为了右边区域，这是一个错误
        // 虽然这个错误并不影响结果，因为合并过程都是一样的逻辑
        // ********
        ListNode* mid = middleNode(head);

        // 2、基于 mid 这个中点，将链表划分为两个区域

        // 左边的区域开头节点是 head
        ListNode* leftHead = head;

        // 右边的区域开头节点是 mid->next
        ListNode* rightHead = mid->next;

        // 将链表断开，就形成了两个链表了
        mid->next = nullptr;

        // 3、将右边的链表进行反转
        rightHead = reverseList(rightHead);

        // 4、将这两个链表进行合并操作，即进行【交错拼接】
        while( leftHead != nullptr && rightHead != nullptr){

            // 拼接过程如下
            // 5、先记录左区域、右区域【接下来将有访问的两个节点】
            ListNode* leftHeadNext = leftHead->next;

            ListNode* rightHeadNext = rightHead->next;

            // 6、左边连接右边的开头
            leftHead->next = rightHead;

            // 7、leftHead 已经处理好，移动到下一个节点，即刚刚记录好的节点
            leftHead = leftHeadNext;

            // 8、右边连接左边的开头
            rightHead->next = leftHead;

            // 9、rightHead 已经处理好，移动到下一个节点，即刚刚记录好的节点
            rightHead = rightHeadNext;
            
        }
    }

    

    ListNode* middleNode(ListNode*  head) {
        ListNode* slow = head;
        ListNode* fast = head;
        while (fast != nullptr && fast->next != nullptr) {
            slow = slow->next;
            fast = fast->next->next;
        }
        return slow;
    }


public:
    ListNode* reverseList(ListNode* head) {

        // 寻找递归终止条件
        // 1、head 指向的结点为 null 
        // 2、head 指向的结点的下一个结点为 null 
        // 在这两种情况下，反转之后的结果还是它自己本身
        if( head == NULL || head->next == NULL)  return head;

        // 不断的通过递归调用，直到无法递归下去，递归的最小粒度是在最后一个节点
        // 因为到最后一个节点的时候，由于当前节点 head 的 next 节点是空，所以会直接返回 head
        ListNode *cur = reverseList(head->next);

        // 比如原链表为 1 --> 2 --> 3 --> 4 --> 5
        // 第一次执行下面代码的时候，head 为 4，那么 head.next = 5
        // 那么 head.next.next 就是 5.next ，意思就是去设置 5 的下一个节点
        // 等号右侧为 head，意思就是设置 5 的下一个节点是 4

        // 这里出现了两个 next
        // 第一个 next 是「获取」 head 的下一节点
        // 第二个 next 是「设置」 当前节点的下一节点为等号右侧的值
        head->next->next = head;


        // head 原来的下一节点指向自己，所以 head 自己本身就不能再指向原来的下一节点了
        // 否则会发生无限循环
        head->next = nullptr;

        // 我们把每次反转后的结果传递给上一层
        return cur;

    }
    
};

3、Python 代码

class Solution:
    def reorderList(self, head: ListNode) -> None:
        # a、寻找出原链表的中点，把链表划分为两个区域
        # b、将右边的链表进行反转
        # c、把这两个区域进行交错合并
      
        # 1、使用快慢指针寻找出链表的中点来 
        # ********
        # 对于 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8
        # 中间节点值为 5
        # 所以左边区域为 1 -> 2 -> 3 -> 4 -> 5
        # 右边区域为 6 -> 7 -> 8
        # 但在视频讲解中，我把 5 归为了右边区域，这是一个错误
        # 虽然这个错误并不影响结果，因为合并过程都是一样的逻辑
        # ********
        mid = self.middleNode(head)

        # 2、基于 mid 这个中点，将链表划分为两个区域

        # 左边的区域开头节点是 head
        leftHead = head

        # 右边的区域开头节点是 mid.next
        rightHead = mid.next

        # 将链表断开，就形成了两个链表了
        mid.next = None

        # 3、将右边的链表进行反转
        rightHead = self.reverseList(rightHead)

        # 4、将这两个链表进行合并操作，即进行【交错拼接】
        while leftHead and rightHead :

            # 拼接过程如下
            # 5、先记录左区域、右区域【接下来将有访问的两个节点】
            leftHeadNext = leftHead.next

            rightHeadNext = rightHead.next

            # 6、左边连接右边的开头
            leftHead.next = rightHead

            # 7、leftHead 已经处理好，移动到下一个节点，即刚刚记录好的节点
            leftHead = leftHeadNext

            # 8、右边连接左边的开头
            rightHead.next = leftHead

            # 9、rightHead 已经处理好，移动到下一个节点，即刚刚记录好的节点
            rightHead = rightHeadNext
    


    def middleNode(self, head: ListNode) -> ListNode:
        slow = fast = head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
        return slow
    
    def reverseList(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        # 寻找递归终止条件
        # 1、head 指向的结点为 null 
        # 2、head 指向的结点的下一个结点为 null 
        # 在这两种情况下，反转之后的结果还是它自己本身
        if(head == None or head.next == None):
            return head

        # 不断的通过递归调用，直到无法递归下去，递归的最小粒度是在最后一个节点
        # 因为到最后一个节点的时候，由于当前节点 head 的 next 节点是空，所以会直接返回 head
        cur = self.reverseList(head.next)

        # 比如原链表为 1 --> 2 --> 3 --> 4 --> 5
        # 第一次执行下面代码的时候，head 为 4，那么 head.next = 5
        # 那么 head.next.next 就是 5.next ，意思就是去设置 5 的下一个节点
        # 等号右侧为 head，意思就是设置 5 的下一个节点是 4

        # 这里出现了两个 next
        # 第一个 next 是「获取」 head 的下一节点
        # 第二个 next 是「设置」 当前节点的下一节点为等号右侧的值
        head.next.next = head

        # 原来的下一节点指向自己，所以 head 自己本身就不能再指向原来的下一节点了
        # 否则会发生无限循环
        head.next = None

        # 我们把每次反转后的结果传递给上一层
        return cur

四、复杂度分析

**时间复杂度：**O(N)，其中 N 是链表中的节点数。

**空间复杂度：**O(1)。